'''
Created on 2011-7-4

@author: koala
'''
def dtw (a, b):
    distance = []
    output = []
    
    for i in range(len(a)):
        distance.append([])
        for j in range(len(b)):
            distance[i].append((b[j]-a[i])*(b[j]-a[i]))
            
    for i in range(0, len(a)):
        output.append([])
        for j in range(len(b)):
            output[i].append(0)
    
    output[0][0] = distance[0][0]
    for i in range(1, len(a)):
        output[i][0] = output[i-1][0] + distance[i][0]
        
    for j in range(1, len(b)):
        output[0][j] = output[0][j-1] + distance[0][j]

    for i in range(1, len(a)):
        for j in range(1, len(b)):
            output[i][j] += min(output[i-1][j-1],output[i][j-1],output[i-1][j]) + distance[i][j]
            
    min_d = output[0][len(b)-1]
    min_start = 0
    min_end = 0

    for i in range(0, len(a)):
        if min_d > output[i][len(b)-1]:
            min_d = output[i][len(b)-1]
            min_end = i
    print min_d
    
    return min_d, min_end;

a = [1,1,1,10,2,3]
b = [1,1,1,2,10,3]
dtw(a,b)
